package com.github.hgkmail.hello.leetcode101.pointer.linkedlist;

import com.github.hgkmail.hello.leetcode101.base.ListNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LC160IntersectionOfTwoLinkedLists {
    //使用hashmap保存父节点，逆向查找
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null || headB==null) {
            return null;
        }
        //引入 dummyHead
        ListNode dummyHeadA = new ListNode(0, headA);
        ListNode dummyHeadB = new ListNode(0, headB);
        //引入tail
        ListNode tailA, tailB;
        //引入HashMap存放parent，用于后面查找
        Map<ListNode, ListNode> parentA = new HashMap<>();
        Map<ListNode, ListNode> parentB = new HashMap<>();

        ListNode curr = dummyHeadA;
        while (curr.next!=null) {
            parentA.put(curr.next, curr);
            curr = curr.next;
        }
        tailA=curr;

        curr = dummyHeadB;
        while (curr.next!=null) {
            parentB.put(curr.next, curr);
            curr = curr.next;
        }
        tailB=curr;

        ListNode i=tailA, j=tailB;
        while (i==j) { //相同节点，继续往起点查找
            i=parentA.get(i);
            j=parentB.get(j);
        }
        return i.next;
    }

    //使用hashset，第一个相同的节点一定是相交的节点
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> setA = new HashSet<>();
        ListNode curr=headA;
        while (curr!=null) {
            setA.add(curr);
            curr=curr.next;
        }

        curr=headB;
        while (curr!=null) {
            if (setA.contains(curr)) {
                return curr;
            }
            curr=curr.next;
        }

        return null;
    }

    public static void main(String[] args) {
        ListNode c = new ListNode(3, null);
        ListNode a = new ListNode(2, c);
//        ListNode b = new ListNode(2, c);
        System.out.println(new LC160IntersectionOfTwoLinkedLists().getIntersectionNode2(c, c));
    }
}
